//
// Created by francklinson on 2021/7/8.
//
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Solution {
public:
    /**
     * bfs 将所有联通在一起的城市放到一起
     * @param isConnected
     * @return
     */
    int findCircleNum(vector<vector<int>> &isConnected) {
        int ans = 0;
        int cityNum = (int) isConnected.size();
        vector<bool> seen(cityNum, false);
        queue<int> q;
        for (int i = 0; i < cityNum; ++i) {
            if (!seen[i]) {
                /// 执行bfs
                q.push(i);
                while (!q.empty()) {
                    auto p = q.front();
                    q.pop();
                    seen[p] = true;
                    for (int j = 0; j < cityNum; ++j) {
                        if (isConnected[p][j] == 1 and seen[j] == false)
                            q.push(j);
                    }
                }
                ++ans;
            }
        }
        return ans;
    }
};

class Solution2 { /// 题解 dfs
public:
    void dfs(vector<vector<int>> &isConnected, vector<int> &visited, int provinces, int i) {
        for (int j = 0; j < provinces; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = 1; /// 每次调用dfs的作用就是写标记
                dfs(isConnected, visited, provinces, j);
            }
        }
    }

    int findCircleNum(vector<vector<int>> &isConnected) {
        int provinces = isConnected.size();
        vector<int> visited(provinces);
        int circles = 0;
        for (int i = 0; i < provinces; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, provinces, i);
                circles++;
            }
        }
        return circles;
    }
};


int main() {
    vector<vector<int>> isConnected{{1, 0, 0},
                                    {0, 1, 0},
                                    {0, 0, 1}};
    Solution sol;
    cout << sol.findCircleNum(isConnected) << endl;
    return 0;
}